|
In the mathematical field of graph theory, the ladder graph ''L''''n'' is a planar undirected graph with ''2n'' vertices and ''n+2(n-1)'' edges. The ladder graph can be obtained as the Cartesian product of two path graphs, one of which has only one edge: ''L''''n'',1 = ''P''''n'' × ''P''1.〔Hosoya, H. and Harary, F. "On the Matching Properties of Three Fence Graphs." J. Math. Chem. 12, 211-218, 1993.〕〔Noy, M. and Ribó, A. "Recursively Constructible Families of Graphs." Adv. Appl. Math. 32, 350-363, 2004.〕 Adding two more crossed edges connecting the four degree-two vertices of a ladder graph produces a cubic graph, the Möbius ladder. By construction, the ladder graph L''n'' is isomorphic to the grid graph ''G''2,''n'' and looks like a ladder with ''n'' rungs. It is Hamiltonian with girth 4 (if ''n>1'') and chromatic index 3 (if ''n>2''). The chromatic number of the ladder graph is 2 and its chromatic polynomial is . ==Gallery== Image:Ladder graph L8 2COL.svg|The chromatic number of the ladder graph is 2. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Ladder graph」の詳細全文を読む スポンサード リンク
|